package 字符串的排列;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

//题目描述
//输入一个字符串,按字典序打印出该字符串中字符的所有排列。
// 例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
public class Solution
{

    public ArrayList<String> PermutationHelp(StringBuilder str)
    {
        ArrayList<String> result = new ArrayList<String>();
        if (str.length() == 1) result.add(str.toString());
        else
        {
            for (int i = 0; i < str.length(); i++)
            {
                if (i == 0 || str.charAt(i) != str.charAt(0))
                {
                    swap(str, i, 0);
                    ArrayList<String> newResult = PermutationHelp(new StringBuilder(str.substring(1)));
                    for (int j = 0; j < newResult.size(); j++)
                        result.add(str.substring(0, 1) + newResult.get(j));
                    //用完还是要放回去的
                    swap(str, i, 0);
                }
            }
            //需要在做一个排序操作
            Collections.sort(result);
        }
        return result;
    }

    public void swap(StringBuilder str, int index1, int index2)
    {
        char temp = str.charAt(index1);
        str.setCharAt(index1, str.charAt(index2));
        str.setCharAt(index2, temp);
    }

    public ArrayList<String> Permutation(String str)
    {
        StringBuilder strBuilder = new StringBuilder(str);
        ArrayList<String> result = PermutationHelp(strBuilder);
        return result;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        System.out.println(solution.Permutation("abc"));
    }

}
